/*
 * @Author: szx
 * @Date: 2022-05-05 14:43:47
 * @LastEditTime: 2022-05-05 15:19:08
 * @Description:
 * @FilePath: \leetcode\剑指offerII\110\110.js
 */
var calcEquation = function (equations, values, queries) {
    let nvars = 0;
    const variables = new Map();
    const n = equations.length;
    for (let i = 0; i < n; i++) {
        if (!variables.has(equations[i][0])) variables.set(equations[i][0], nvars++);
        if (!variables.has(equations[i][1])) variables.set(equations[i][1], nvars++);
    }

    // edges就是邻接表
    const edges = new Array(nvars).fill(0).map(() => []);
    for (let i = 0; i < n; i++) {
        const va = variables.get(equations[i][0]),
            vb = variables.get(equations[i][1]);
        edges[va].push([vb, values[i]]);
        edges[vb].push([va, 1.0 / values[i]]);
    }

    const queriesCount = queries.length;
    const ret = [];
    for (let i = 0; i < queriesCount; i++) {
        const query = queries[i];
        let result = -1.0;
        if (variables.has(query[0]) && variables.has(query[1])) {
            const ia = variables.get(query[0]),
                ib = variables.get(query[1]);
            if (ia === ib) {
                // 存在并且相同就返回1
                result = 1.0;
            } else {
                // 从源头开始查找
                const points = [ia];
                const ratios = new Array(nvars).fill(-1.0);
                ratios[ia] = 1.0;

                while (points.length && ratios[ib] < 0) {
                    const x = points.pop();
                    for (const [y, val] of edges[x]) {
                        if (ratios[y] < 0) {
                            ratios[y] = ratios[x] * val;
                            points.push(y);
                        }
                    }
                }
                result = ratios[ib];
            }
        }
        ret[i] = result;
    }
    return ret;
};

var calcEquation = function (equations, values, queries) {
    let nvars = 0;
    const variables = new Map(),
        n = equations.length;
    for (let i = 0; i < n; i++) {
        if (!variables.has(equations[i][0])) variables.set(equations[i][0], nvars++);
        if (!variables.has(equations[i][1])) variables.set(equations[i][1], nvars++);
    }
    // 邻接矩阵
    const graph = new Array(nvars).fill(0).map(() => new Array(nvars).fill(-1.0));
    for (let i = 0; i < n; i++) {
        const va = variables.get(equations[i][0]),
            vb = variables.get(equations[i][1]);
        graph[va][vb] = values[i];
        graph[vb][va] = 1.0 / values[i];
    }

    // Floyd算法，O(n^3)的时间复杂度，O(n^2)的空间复杂度
    // 1、遍历所有的点
    for (let k = 0; k < nvars; k++) {
        // 2、遍历开始的点
        for (let i = 0; i < nvars; i++) {
            // 3、遍历结束的点
            for (let j = 0; j < nvars; j++) {
                // 4、如果有开始的点到中间的点 和 中间的点到结束的点，那么就更新开始到结束的点的权重
                if (graph[i][k] > 0 && graph[k][j] > 0) {
                    graph[i][j] = graph[i][k] * graph[k][j];
                }
            }
        }
    }

    const queriesCount = queries.length;
    const res = new Array(queriesCount).fill(0);
    for (let i = 0; i < queriesCount; i++) {
        const query = queries[i];
        let result = -1.0;
        // 先判断分母和分子有没有这两个数
        if (variables.has(query[0]) && variables.has(query[1])) {
            const ia = variables.get(query[0]),
                ib = variables.get(query[1]);
            if (graph[ia][ib] > 0) {
                result = graph[ia][ib];
            }
        }
        res[i] = result;
    }
    return res;
};
